【题解】 [AH2017/HNOI2017]大佬 搜索+DP luoguP3724/bzoj4828 | Qiuly's blog!

【题解】 [AH2017/HNOI2017]大佬 搜索+DP luoguP3724/bzoj4828

Posted on | Edited on | In | Comments:

首先可以发现，刷水题跟打伤害是可以分开处理的。

我们先用 $DP$ 预处理出能打伤害的最大天数，其余的天数都只能用刷水题的方式恢复。

于是设 $dp[i][j]$ 表示前 $i$ 天，信心值还剩 $j$ 的能够打伤害的最大天数。

可以知道一天只有两种情况，我们枚举 $i,j​$ 然后进行转移：

  • 如果可以坚持到下一天：dp[i+1][j-a[i+1]]=max(dp[i+1][j-a[i+1]],dp[i][j]+1)
  • 如果是要刷水题：dp[i+1][j-a[i+1]+w[i+1]]=max(dp[i+1][j-a[i+1]+w[i+1]],dp[i][j])

当然，如果要做第一个转移的话得先判断一下 j-a[i+1] 是否超了界，超界了的话当然就不能转移了。第二个转移也要注意，j-a[i+1]+w[i+1] 先要跟信心上界($mc$) 取 $min$ 。

最后在所有的状态中取一个最大值即可。

Code-DP

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
inline void DP_maxday(){
    memset(dp,-1,sizeof(dp));//初始化
    dp[0][mc]=0;
    for(int i=0;i<n;++i)
        for(int j=0;j<=mc;++j){
            if(dp[i][j]<0)continue;
            int t1=j-a[i+1];if(t1<0)continue;
            dp[i+1][t1]=max(dp[i+1][t1],dp[i][j]+1);
            int t2=min(t1+w[i+1],mc);
            dp[i+1][t2]=max(dp[i+1][t2],dp[i][j]);
        }
    for(int i=1;i<=n;++i)
        for(int j=0;j<=mc;++j)
            d=max(d,dp[i][j]);
    return;
}

这个 $d$ 就是我们能够打伤害的最大天数。

然后我们需要预处理出打出伤害的所有状态，这里我用广搜。

队列的结构体 $Node$ 由三个元素组成：$F,L,D$ ，表示在第 $D$ 天，你的 $F$ 的值为 $F$ ，$L$ 的值为 $L$ 。

然后就是转移，这里也是两种情况：

  • 使讽刺能力乘上等级：F,L,D -> F*L,L,D+1 (L>0)
  • 使等级加一：F,L,D -> F,L+1,D+1

直接这样转移就好了，注意我们需要开个数组将这些打出伤害的方案记下来，当然，记录的时候不用记 $L$ ，因为后面打伤害的时候 $L$ 是没太多用的。

还有就是每次需要判断一下当前的天数，如果当前状态的天数已经大于了 $d$ 那么当前状态显然是不合法的。

最后就是需要用 $map$ 判个重，不然的话会爆炸，当然判重的时候也不要判 $L$ 。

Code-Bfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
map<pair<int,int>,int> vis;
inline void BFS_maxhurt(){
    q.push((Node){1,0,1});//初始化
    while(!q.empty()){
        Node x=q.front();q.pop();
        if(x.D>d)continue;
        else if(x.D==d){T[++cnt]=(Data){x.F,x.D};continue;}
        else T[++cnt]=(Data){x.F,x.D};
        /*第一种转移*/
        if(x.L&&(ll)x.F*x.L<=1e8&&!vis[pair<int,int>(x.F*x.L,x.L)]){
            q.push((Node){x.F*x.L,x.L,x.D+1});
            vis[pair<int,int>(x.F*x.L,x.L)]=x.D;//标记
        }
        /*第二种转移*/
        if(!vis[pair<int,int>(x.F,x.L+1)]){
            q.push((Node){x.F,x.L+1,x.D+1});
            vis[pair<int,int>(x.F,x.L+1)]=x.D;//标记
        }
    }return;
}

抱歉我的英语真的不好

然后我们已经将所有可行的打伤害的方案记录到 $T​$ 数组里面了，接下来就是看看怎么用这些方案打大佬了。

首先还嘴是可以直接算的，这个是不用考虑的。我们唯一要处理的就是怼大佬，我们可以选择怼一次还是两次。可以发现怼一次的话直接枚举 $T​$ 数组中的方案即可，算上天数，剩下的天数当然是每天还嘴，看看这样可不可以干掉大佬：

1
if(T[i].F<=C&&T[i].D<=d&&C-T[i].F<=d-T[i].D)return true;

( $C$ 为当前大佬的信心值)

首先，T[i].F<=C 是为了保证你不被虐飞，然后 T[i].D<=d 当然就是你有足够的天数来实现这个方案，最后的 C-T[i].F<=d-T[i].D 就是看看打完这个方案后剩下的天数能否通过仅剩的还嘴来干掉大佬。

那么如果是怼两次大佬呢？

可以发现其实跟上面差不多，设两次中一次是第 $i$ 套方案，一次是第 $j$ 套方案。那么首先这两套方案的 $F$ 的和不能超过 $C$ ，然后就是要保证剩下的天数中可以通过还嘴干掉大佬，于是我们可以列出式子：

然后前式很容易满足，我们来看看后式：

我们枚举一个 $i$ ，寻找 $j$ 。既然 $i$ 已经确定，最优的 $j$ 一定满足 $T[j].F-T[j].D$ 最大，取 $max$ 就好。

至于代码的问题，我们先将 $T[i]$ 按照 $F$ 排序，然后按顺序寻找 $j$ ，代码实现就不是很难了。

Code-Solve:

1
2
3
4
5
6
7
8
9
10
11
12
13
inline bool solve(int C){
    if(C<=d)return true;//可以全程顶嘴干掉大佬，直接retrun
    int l=0,mx=-inf;//初始化
    for(int i=cnt;i>=1;--i){
        /*用第i方案怼一次可以干掉大佬，return*/
        if(T[i].F<=C&&T[i].D<=d&&C-T[i].F<=d-T[i].D)return true;
        /*按顺序扫描满足要求的 j*/
        while(l<cnt&&T[i].F+T[l+1].F<=C)
            l++,mx=max(mx,T[l].F-T[l].D);//取max
        /*可以怼两次干掉大佬，return*/
        if(T[i].F-T[i].D+mx+d>=C)return true;
    }return false;//干不掉大佬了
}

当然这个时间复杂度很玄学，大概是 $O($状态数$)$ 。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;

const int N=1.5e2+2;
const int S=1e7+5;
const int inf=1e9+9;

int n,m,mc,a[N],w[N];
int d,dp[N][N],cnt;
struct Node{int F,L,D;};
struct Data{
    int F,D;
    bool operator < (const Data&x)const{return F<x.F;}
}T[S];
map<pair<int,int>,int> vis;
queue<Node> q;

template <typename _Tp> inline void IN(_Tp&x){
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    if(flag)x=-x;
}

inline void DP_maxday(){
    memset(dp,-1,sizeof(dp));
    dp[0][mc]=0;
    for(int i=0;i<n;++i)
        for(int j=0;j<=mc;++j){
            if(dp[i][j]<0)continue;
            int t1=j-a[i+1];if(t1<0)continue;
            dp[i+1][t1]=max(dp[i+1][t1],dp[i][j]+1);
            int t2=min(t1+w[i+1],mc);
            dp[i+1][t2]=max(dp[i+1][t2],dp[i][j]);
        }
    for(int i=1;i<=n;++i)
        for(int j=0;j<=mc;++j)
            d=max(d,dp[i][j]);
    return;
}

inline void BFS_maxhurt(){
    q.push((Node){1,0,1});
    while(!q.empty()){
        Node x=q.front();q.pop();
        if(x.D>d)continue;
        else if(x.D==d){T[++cnt]=(Data){x.F,x.D};continue;}
        else T[++cnt]=(Data){x.F,x.D};
        if(x.L&&(ll)x.F*x.L<=1e8&&!vis[pair<int,int>(x.F*x.L,x.L)]){
            q.push((Node){x.F*x.L,x.L,x.D+1});
            vis[pair<int,int>(x.F*x.L,x.L)]=x.D;
        }
        if(!vis[pair<int,int>(x.F,x.L+1)]){
            q.push((Node){x.F,x.L+1,x.D+1});
            vis[pair<int,int>(x.F,x.L+1)]=x.D;
        }
    }return;
}

inline bool solve(int C){
    if(C<=d)return true;
    int l=0,mx=-inf;
    for(int i=cnt;i>=1;--i){
        if(T[i].F<=C&&T[i].D<=d&&C-T[i].F<=d-T[i].D)return true;
        while(l<cnt&&T[i].F+T[l+1].F<=C)
            l++,mx=max(mx,T[l].F-T[l].D);
        if(T[i].F-T[i].D+mx+d>=C)return true;
    }return false;
}

int main(){
    IN(n),IN(m),IN(mc);
    for(int i=1;i<=n;++i)IN(a[i]);
    for(int i=1;i<=n;++i)IN(w[i]);
    DP_maxday();
    BFS_maxhurt();
    sort(T+1,T+cnt+1);
    for(int i=1;i<=m;++i){
        int C;IN(C);
        if(solve(C))printf("1\n");
        else printf("0\n");
    }
    return 0;
}

本文标题:【题解】 [AH2017/HNOI2017]大佬 搜索+DP luoguP3724/bzoj4828

文章作者:Qiuly

发布时间:2019年03月21日 - 00:00

最后更新:2019年03月29日 - 14:09

原始链接:http://qiulyblog.github.io/2019/03/21/[题解]bzoj4828/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。